A computer network is a geographically distributed collection of interconnected communication links and segments for transporting data between nodes, such as computers. Many types of network segments are available, with the types ranging from local area networks (LAN) to wide area networks (WAN). For example, the LAN may typically connect personal computers and workstations over dedicated, private communications links, whereas the WAN may connect large numbers of nodes over long-distance communications links, such as common carrier telephone lines. The Internet is an example of a WAN that connects disparate networks throughout the world, providing global communication between nodes on various networks. The nodes typically communicate over the network by exchanging discrete frames or packets of data according to predefined protocols. In this context, a protocol consists of a set of rules defining how the nodes interact with each other.
Computer networks may be further interconnected by an intermediate network node, such as a switch or router, having a plurality of ports that may be coupled to the networks. To interconnect dispersed computer networks and/or provide Internet connectivity, many organizations rely on the infrastructure and facilities of Internet Service Providers (ISPs). ISPs typically own one or more backbone networks that are configured to provide high-speed connection to the Internet. To interconnect private networks that are geographically diverse, an organization may subscribe to one or more ISPs and couple each of its private networks to the ISP's equipment. Here the router may be utilized to interconnect a plurality of private networks or subscribers to an IP “backbone” network. Routers typically operate at the network layer, i.e., layer 3, of a communications protocol stack, such as the internetwork layer of the Transmission Control Protocol/Internet Protocol (TCP/IP) communications architecture.
Simple networks may be constructed using general-purpose routers interconnected by links owned or leased by ISPs. As networks become more complex with greater numbers of elements, additional structure may be required. In a complex network, structure can be imposed on routers by assigning specific jobs to particular routers. A common approach for ISP networks is to divide assignments among access routers and backbone routers. An access router provides individual subscribers access to the network by way of large numbers of relatively low-speed ports connected to the subscribers. Backbone routers, on the other hand, provide transports to Internet backbones and are configured to provide high forwarding rates on fast interfaces. ISPs may impose further physical structure on their networks by organizing them into points of presence (POP). An ISP network usually consists of a number of POPs, each of which comprises a physical location wherein a set of access and backbone routers is located.
As Internet traffic increases, the demand for access routers to handle increased density and backbone routers to handle greater throughput becomes more important. In this context, increased density denotes a greater number of subscriber ports that can be terminated on a single router. Such requirements can be met most efficiently with platforms designed for specific applications. An example of such a specifically designed platform is an aggregation router. The aggregation router is an access router configured to provide high quality of service and guaranteed bandwidth for both data and voice traffic destined for the Internet. The aggregation router also provides a high degree of security for such traffic. These functions are considered “high-touch” features that necessitate substantial processing of the traffic by the router. More notably, the aggregation router is configured to accommodate increased density by aggregating a large number of leased lines from ISP subscribers onto a few trunk lines coupled to an Internet backbone.
In a typical implementation of a router, a processor is provided to process an original header of a packet while leaving the remainder of the packet, i.e., the “trailer”, unchanged. In a high-end router implementation using a network processor, dedicated hardware is provided to efficiently pass the original packet header to a forwarding engine. The forwarding engine may be implemented as a “chip”, e.g., an application specific integrated circuit (ASIC), comprising a plurality of processors operating in a serial “pipeline” configuration to process (modify) the packet header. Only the original packet header is brought “on-chip” to reduce the memory and bandwidth requirements for the forwarding engine; the entire packet, including the packet trailer, is held in a small buffer of the dedicated hardware.
As part of the packet header processing, the processors may parse (“strip off”) portions of the original packet header, such as a layer 2 header or a tunnel header, and examine a layer 3 header or a layer 4 header to determine the destination for the packet. The processors may further modify portions of the layer 3 or 4 headers and add new headers associated with the outgoing interface or tunnel. Once the packet header has been modified, it is rejoined (merged) with the packet trailer and placed into a buffer of an external memory. Thereafter, the merged packet is “queued” (i.e., placed on an output queue) to an output interface or link where it awaits output scheduling.
There are several advantages to not placing the original packet into the external memory buffer until packet header processing has been completed. In some implementations, there may be separate output buffers (per outgoing interface) such that selection of an output buffer is not determined until after packet processing. Even in cases where a single memory is used for the output buffers, it is more “memory bandwidth” efficient to write (move) the modified packet header at the same time as the packet trailer. In order to move the entire merged packet to an output buffer at one time, the entire original packet beyond the packet header must be held for the time that it takes the pipeline of processors to complete the packet header processing.
As noted, the small buffer, e.g., an internal packet memory buffer, of the dedicated hardware is typically used to hold the entire original packet, including the packet header. The dedicated hardware may also be embodied as an ASIC chip. Since the internal packet buffer is “small”, it may be implemented on the dedicated hardware chip along with direct memory access (DMA) logic and external memory interface logic. The minimum size of the packet buffer is determined by a maximum packet size plus the time needed to process a packet header through the processor pipeline. If the hardware chip is coupled to multiple line cards of the router via multiple links, multiple internal packet buffers may be required. To enable these buffers to be implemented “on-chip”, their sizes must be kept as small as possible. Therefore, each internal packet buffer may not comprise a binary number of entries in length. Moreover, the packets are typically stored sequentially in the packet buffer to optimize usage of that memory resource and, therefore, may not start on binary boundaries.
When an original packet header is passed to the processors, a pointer is provided to the processors indicating a location of the original packet in the internal packet buffer. When the processors create the new modified packet header, they may issue DMA commands to move the modified header, along with the packet trailer from packet buffer as specified by an internal packet buffer address, to the external memory buffer. Since the internal packet buffer may contain the entire packet including the original packet header that has been subsequently modified, the DMA command typically specifies the location within the buffers as a displacement from the address of the original entire packet, computed based upon the new modified packet header.